package algorithm.swordoff;

/**
 * 调整数组顺序使奇数位于偶数前面
 *
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
 * 要求程序实现扩展性, 可以使用户自定义一个逻辑, 符合要求的放在前面, 不符合要求的放在数组的后面
 *
 * 快速排序的变体
 */

public class SQ21 {

    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            // 注意不是left和right比的话,是自己和自己比,结果需要判断这个数是不是放在前面
            while (left < right && isHead(nums[right])) right--;
            swap(nums, left, right);
            while (left < right && !isHead(nums[left])) left++;
            swap(nums, left, right);
        }
        return nums;
    }

    public static int[] swap(int[] arr, int m, int n) {
        int temp = arr[m];
        arr[m] = arr[n];
        arr[n] = temp;
        return arr;
    }

    public static boolean isHead(int num) {
        return num % 3 == 0;
    }

    public static void main(String[] args) {
        int[] a = {3, 7, 4, 5, 6, 9, 10};
        Character[] ccc = {3, 7, 4, 5, 6, 9, 10};
        SQ21 sto = new SQ21();
        int[] b = sto.exchange(a);
        for (int i = 0; i < b.length; i++) {
            System.out.println(b[i]);
        }
    }

}
